package num208;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/5/10 1:50
 * @Desc :
 */
public class Trie {
  Trie[] alphabet = new Trie[26];
  boolean isEnd = false;

  public Trie() {
  }

  /**
   * Inserts a word into the trie.
   */
  public void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      if (node.alphabet[c - 'a'] == null)
        node.alphabet[c - 'a'] = new Trie();
      node = node.alphabet[c - 'a'];
    }
    node.isEnd = true;
  }

  /**
   * Returns if the word is in the trie.
   */
  public boolean search(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
      node = node.alphabet[c - 'a'];
      if (node == null) return false;
    }
    return node.isEnd;
  }

  /**
   * Returns if there is any word in the trie that starts with the given prefix.
   */
  public boolean startsWith(String prefix) {
    Trie node = this;
    for (char c : prefix.toCharArray()) {
      node = node.alphabet[c - 'a'];
      if (node == null) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Trie1 trie = new Trie1();
    trie.insert("apple");
    trie.insert("app");
    System.out.println(trie.search("app"));
    System.out.println(trie.search("apple"));
    //System.out.println(trie.startsWith("heq"));
  }
}
